This invention pertains to a method and device for compressing portions of images. In particular, it applies to encoding images and sequences of images, especially for the purpose of transmitting them over a computer network, such as the Internet, or for storing them on a digital information medium. This method and device may be integrated into any system with the ability to compress and then decompress any portion of an image on all hardware platforms.
Certain video encoding methods use predictive methods with residual encoding. FIG. 1 depicts a device implementing such a method, in the form of a block diagram. A prediction made by the function 102, of one portion of an original image 101 is created based on other portions of one or more images appearing before or after the image being encoded, or other elements of the current image. The residual 103 is obtained through the difference 105 between the prediction and the original. The residual 103 and the prediction 102 are encoded in the sent video stream by the encoding function 104.
This method is typically used to take advantage of the temporal redundancy of a sequence of images. It is particularly often-used in the compression system of the ISO/ITU/MPEG and H.261/3/4 standards. As depicted in FIG. 2, which, in the form of a flowchart, depicts the prior art for MPEG (“Moving Picture Expert Group”) compression, the motion compensation is based on comparing a given block of the current image to a set of blocks or sub-blocks of the current image, or other images appearing before or after the current image. A comparative measurement is taken between the blocks. If the measurement of the difference is below a certain threshold, the blocks are considered to be similar, and the difference in position is indicated by a motion vector.
Known video compression standards, such as MPEG, use the two groups of steps 200 and 210, described with reference to FIG. 2, to compress the images of a video stream into non-intra images, meaning images which are encoded with reference to other images of the video stream.
Motion estimation 200 consists of encoding each image based on elements found in other images of the video stream, known as reference images (often the preceding image, the last intra image, or the next intra image). The steps performed during motion estimation 200 are as follows:                step 201: breaking down the image to be encoded into blocks with a fixed size of W×H pixels (often 16×16);        step 202: for each image block, searching within the reference image of the floating area of W×H pixels that is most similar to the block in question;        step 203: for each block, storing the motion vector that indicates motion (in spatial coordinates) between the block the block and the most similar block found during step 202;        
Motion compensation 210 consists of compressing the residual. The steps performed during motion compensation 210 are, for each block, as follows:                step 214: for each block, calculating the residual, i.e. the difference between the block and the most similar area found.        step 211: compressing the residual, most commonly using a mathematical function, such as DCT (for “discrete cosine transform”);        step 212: storing the compressed residual; and        step 213: returning to step 200 to encode the next block, if any.        
Video decompression is done as follows:                step 221: decompressing one or more intra images (i.e. images encoding without reference to other images of the video stream);        group of steps 230: reconstructing the non-intra images by doing the following for each block:                    step 231: locating the are most similar to another image in the video stream, using the motion vector;            step 232; decompressing the residual; and            step 233; adding the residual to the most similar area in order to obtain the final block, then returning to step 230 for the next block, if any.                        
Thus, when decoding a video stream, blocks of predicted images are predicted based on portions of other images and decoded motion vectors, to which motion compensation factors must be added.
This prior art, in particular, has the disadvantage that the motion compensation factor decoding, compensation calculation and predicted block compensation steps are costly in resources.
In current encoders, different types of optimization are performed during the compensation steps. For example, the motion vector may be chosen based on different criteria: “SAD” (sum of absolute differences) or “SSD” (sum of square differences), which only take the resulting distortion into account. During encoding, multiple types of connections (blocks, motion vectors) may be chosen. Rate distortion optimization (or “RDO”) is used and takes into account the rate at which the information is transmitted (the size taken within the stream) and the distortion caused by this information (relevance of information). The purpose of RDO is to locate a compromise between the rate used by the encoded stream and the relevance of the information to be encoded.
The RDO algorithm may be used during motion compensation. For example, in patent application US2003/0063667 entitled “Optimal encoding of motion compensated video” and dated May 29, 2002, the step of estimating motion between two images provides multiple possible motion vectors to choose from. Each motion vector is then transformed in the same way as though it has been transformed to be encoded into the video stream, then is decoded in the same way as though it had been decoded from the video stream. The distortion between the original block and the encoded and then decoded block, calculated after decoding the motion vector, is determined for each possible motion vector. The motion vector which minimizes the distortion and rate is chosen.
Generally, motion compensation is used to save on rate and distortion costs. Patent application EP0866622 entitled “Video data compression method” defines a performance measurement (which takes encoding parameters into account) which is applied to the motion compensation step, for the purpose of improving the measurement of rate and distortion costs.
In En-hui Yang and Xiang Yu's article “Rate Distortion Optimization in H.264”, published during the workshop organized for the inauguration of the “Information Theory and Applications Center” in February 2006, the RDO algorithm makes it possible to establish a flexible decision criterion for choosing factor encoding criteria. A tree is created, the nodes of which represent different encoding steps and measure the resulting rate and distortion costs. The tree is then traveled, taking the best path (minimizing rate and distortion costs) to obtain the most relevant choice of encoding for the rate and distortion resulting from the factor encoding.
In patent application FR2850827 entitled “Procèdè et dispositif de compression de parties d'images” (“Method and device for compressing portions of images”), the step of motion compensation is eliminated. However, in some cases, the visual output is noticeably worse.